/*
 * Heapsort is a much more efficient version of selection sort. It also works by determining 
 * the largest (or smallest) element of the list, placing that at the end (or beginning) of 
 * the list, then continuing with the rest of the list, but accomplishes this task efficiently 
 * by using a data structure called a heap, a special type of binary tree. Once the data list has
 * been made into a heap, the root node is guaranteed to be the largest element. It is removed 
 * and placed at the end of the list, then the heap is rearranged so the largest element remaining 
 * moves to the root . Using the heap, finding the next largest element takes O(log n) time, instead 
 * of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time.
 *
 */

#include <iostream>
using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

void print_array(int* a, int n, char* sep=" "){
	for(int i=0;i<n;i++){
		cout<<a[i]<<sep;
	}
	cout <<endl;
}

void heapsort(int arr[], unsigned int N)
{
	unsigned int n = N, i = n/2, parent, child;
	int t;

	for (;;) { /* Loops until arr is sorted */
		if (i > 0) { /* First stage - Sorting the heap */
			i--;           /* Save its index to i */
			t = arr[i];    /* Save parent value to t */
		} else {     /* Second stage - Extracting elements in-place */
			n--;           /* Make the new heap smaller */
			if (n == 0) return; /* When the heap is empty, we are done */
			t = arr[n];    /* Save last value (it will be overwritten) */
			arr[n] = arr[0]; /* Save largest value at the end of arr */
		}

		parent = i; /* We will start pushing down t from parent */
		child = i*2 + 1; /* parent's left child */

		/* Shift operation - pushing the value of t down the heap */
		while (child < n){
			if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
				child++; /* Choose the largest child */
			}
			if (arr[child] > t) { /* If any child is bigger than the parent */
				arr[parent] = arr[child]; /* Move the largest child up */
				parent = child; /* Move parent pointer to this child */
				child = parent*2 + 1; /* Find the next child */
			} else {
				break; /* t's place is found */
			}
		}
		arr[parent] = t; /* We save t in the heap */
	}
}

namespace myheapsort{
#define  MAX_HEAPSIZE 200
	class heap{
		public:
			int insert

		private:
			int mheap[MAX_HEAPSIZE];
	}
	void heapsort(int a[], unsigned int N){
	}
}

int main(){
	int array[]={20,2,3,9,1,50,10,5,20};
	int n=sizeof(array)/sizeof(int);
	cout<<"before\n";
	print_array(array,n);

	myheapsort::heapsort(array,n);

	cout<<"after\n";
	print_array(array,n);
}
